The invention relates generally to the field of digital data processing systems, and more specifically to compilers which generate machine-executable code from a high-level language.
Programs detailing the operations to be performed by a digital data processing system, or computer, are in the form of a series of instructions. In response to each instruction, the computer performs one or more operations, as defined by an operation code portion of the instruction, on data which is identified, either explicitly or implicitly, in the instruction. Originally, programmers programmed computers in what was termed "machine language". In machine language, all of the instructions are in the form of sequences of 1s and 0s, which form a binary code that the computers could interpret and use.
Because of the difficulty of programming in machine language, programmers developed forms of programming comprising, first, assembly languages and, later, higher level languages. In an assembly language, a program is also in the form of a sequence of instructions which the computer will process, but the operation code portion is in the form of a mnemonic abbreviation for the operation to occur, and the data to be processed by the instruction is typically identified by a variable name which represents the data's storage location in the computer. An assembler program processes the assembly language program to produce a machine language program which the computer can execute. Since the instructions use mnemonic abbreviations, variable names and/or storage locations, programming using assembly language was greatly simplified over machine language programming.
While assembly language programming made programming less confusing than machine language programming, it was very time-consuming since the programmer had to specify each and every operation to be performed by the computer to solve a problem. Using assembly language programming, the programmer could not limit his attention to the desired high-level arithmetic and logical operations to be performed by the computer in the processing of the algorithm, but instead had to be aware of the operations that the computer would perform in connection with each instruction.
High-level languages were developed to remedy this. High-level languages freed the programmer from having to know the details of operation of the computer, and instead allowed him to concentrate on the algorithms themselves. A compiler program processed the high-level language program to provide a machine-language program which could be executed by the computer, and as a result the compiler program effectively shielded the programmer from the computer. Indeed, programs written in high-level languages may typically be executed, after compilation, on diverse computers which typically can not be done with programs written in assembly language or machine language. A problem with programs written in a high-level language, however, is that they are often somewhat slower than programs written in assembly language which accomplish the same results, and also they can take up much more memory.
To enhance flexibility and reduce the time to actually write a program, some high-level languages permit a programmer to define certain sequences of operations or characteristics as a named generic program structure, called a generic package, generic procedure or generic function, and then use the generic structures elsewhere in the program as they are needed merely by invoking the name and identifying, as parameters, the data to be used in forming the specific structure or performing the specific operations set forth in the previously-defined generic program structure. This permits the programmer to use the program structure which has been previously defined, while at the same time avoiding repeating the program structure or sequence throughout the program. The use of a generic program structure or sequence at a specific location in a program is termed an "instantiation" of the generic program structure or sequence, since it is a specific instance of the structure or sequence, using specific types of data, and so forth.
During compilation of a program including generic program structures or sequences, two methods have been used when a generic program structure or sequence is encountered. In one method, which is the simplest to implement, a code sequence based on the previously defined generic program structure is generated at each instantiation of the generic program structure or sequence in the program which enables the performance of the operations defined in the structure or sequence on the specific forms of data that are identified in the parameters. In this method, depending on the forms of data passed by way of the parameters, the same or similar code sequences may be generated at the diverse instantiation points in the program, which may unduly expand the size of the program.
On the other hand, in another method, during compilation, a single instance of the code sequence is generated which is used at each instantiation of the generic program structure or sequence. The code sequence forming the instantiation must be sufficiently general as to be able to handle any of several types of data passed by way of the parameters which may be identified in the various instantiations. Since the code sequence must be able to handle very general situations, its generality may, in turn, adversely effect performance when the program is run.